package study.datastructure.link.leetcode;/**
 * @program: datastructure
 * @author: lcy
 * @create: 2024-10-11 14:59
 * <p>
 * 2024/10/11,
 */

/**
 2024/10/11,
 */

import study.datastructure.link.SingleLinkList;

import java.awt.*;

/**
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 */
public class Client19 {
    /**
     * 新链表法
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //先找尾
        int i = findTailAndIndex(head);
        if(i==-1){
            return null;
        }
        int deleteIndex = i + 1 - n;
        ListNode prevNode = findByIndex(head, deleteIndex - 1);
        ListNode deleteNode = findByIndex(head, deleteIndex);
        if (deleteIndex == 0) {
            head = head.next;
            return head;
        }
        if (prevNode != null && deleteNode != null) {
            prevNode.next = deleteNode.next;
        }
        return head;
    }
    private ListNode findByIndex(ListNode head, int index) {
        ListNode p;
        int i = 0;//索引
        for (p = head; p != null; p = p.next, i++) {
            if (index == i) {
                return p;
            }
        }
        return null;
    }

    int findTailAndIndex(ListNode head) {
        int i = -1;
        while (head != null) {
            i++;
            head = head.next;
        }
        return i;
    }

    /**
     * 递归法
     * @param head
     * @param n
     * @return
     */

 public ListNode removeNthFromEndByRecursion(ListNode head, int n) {
        ListNode dHead=new ListNode(-1,head);
        recursion(dHead,n);
        return dHead.next;
    }

    private int recursion(ListNode head, int n) {
        if (head == null){
            return 0;
        }
        int nth=recursion(head.next,n);
        if (nth==n){
            head.next=head.next.next;
        }
        return nth+1;
    }

    /**
     * 快慢指针法
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEndByQSP(ListNode head,int n){
     ListNode dHead=new ListNode(-1,head);
     ListNode p1=dHead;
     ListNode p2=dHead;

        for (int i = 0; i < n + 1; i++) {
            p2=p2.next;
        }

        while (p2!=null){
            p1=p1.next;
            p2=p2.next;
        }
        p1.next=p1.next.next;
     return dHead.next;
    }
static int nth=3;

    public static void main(String[] args) {
        ListNode t5=new ListNode(5,null);
        ListNode t4=new ListNode(4,t5);
        ListNode t3=new ListNode(3,t4);
        ListNode t2=new ListNode(2,t3);
        ListNode t1=new ListNode(1,t2);
        Client19 test=new Client19();
      //  System.out.println(test.removeNthFromEndByRecursion(t1, nth));
        System.out.println(test.removeNthFromEndByQSP(t1, nth)); //同时执行有bug 无法正确显示结果
    }
}
